SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Maximum length sequence</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Maximum length sequence</span></span>

</h1>

</header>

<p>

A <b>maximum length sequence</b> (<b>MLS</b>) is a type of <a href="Pseudorandom_binary_sequence" title="Pseudorandom binary sequence">pseudorandom binary sequence</a>.

</p><p>They are bit sequences generated using maximal <a href="Linear-feedback_shift_register" title="Linear-feedback shift register">linear-feedback shift registers</a> and are so called because they are <a href="Periodic_function" title="Periodic function">periodic</a> and reproduce every <a href="Binary_sequence" class="mw-redirect" title="Binary sequence">binary sequence</a> (except the zero vector) that can be represented by the shift registers (i.e., for length-<i>m</i> registers they produce a sequence of length 2<sup><i>m</i></sup> − 1). An MLS is also sometimes called an <b>n-sequence</b> or an <b>m-sequence</b>. MLSs are <a href="Frequency_spectrum" class="mw-redirect" title="Frequency spectrum">spectrally flat</a>, with the exception of a near-zero DC term.

</p><p>These sequences may be represented as coefficients of irreducible polynomials in a <a href="Polynomial_ring" title="Polynomial ring">polynomial ring</a> over <a href="Congruence_subgroup" title="Congruence subgroup">Z/2Z</a>.

</p><p>Practical applications for MLS include measuring <a href="Impulse_response" title="Impulse response">impulse responses</a> (e.g., of room <a href="Reverberation" title="Reverberation">reverberation</a> or arrival times from towed sources in the ocean<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>). They are also used as a basis for deriving pseudo-random sequences in digital communication systems that employ <a href="Direct-sequence_spread_spectrum" title="Direct-sequence spread spectrum">direct-sequence spread spectrum</a> and <a href="Frequency-hopping_spread_spectrum" title="Frequency-hopping spread spectrum">frequency-hopping spread spectrum</a> <a href="Transmission_system" title="Transmission system">transmission systems</a>, and in the efficient design of some <a href="Functional_magnetic_resonance_imaging" title="Functional magnetic resonance imaging">fMRI</a> experiments.<sup id="cite_ref-buracas_2-0" class="reference"><a href="#cite_note-buracas-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Generation">Generation</h2></div>

<p>MLS are generated using maximal <a href="Linear-feedback_shift_register" title="Linear-feedback shift register">linear-feedback shift registers</a>. An MLS-generating system with a shift register of length 4 is shown in Fig. 1. It can be expressed using the following recursive relation:

</p>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{cases}a_{3}[n+1]=a_{0}[n]+a_{1}[n]\\a_{2}[n+1]=a_{3}[n]\\a_{1}[n+1]=a_{2}[n]\\a_{0}[n+1]=a_{1}[n]\\\end{cases}}}</annotation>

</semantics>

</math></span><img src="./f938524a53e278703e9b8b19db795caf70942202.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.171ex; width:27.676ex; height:11.509ex;" alt="{\displaystyle {\begin{cases}a_{3}[n+1]=a_{0}[n]+a_{1}[n]\\a_{2}[n+1]=a_{3}[n]\\a_{1}[n+1]=a_{2}[n]\\a_{0}[n+1]=a_{1}[n]\\\end{cases}}}" loading="lazy"></span></dd></dl>

<p>where <i>n</i> is the time index and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle +}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle +}</annotation>

</semantics>

</math></span><img src="./fe6ef363cd19902d1a7a71fb1c8b21e8ede52406.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle +}" loading="lazy"></span> represents <a href="Modular_arithmetic" title="Modular arithmetic">modulo-2</a> addition. For bit values 0 = FALSE or 1 = TRUE, this is equivalent to the XOR operation.

</p><p>As MLS are periodic and shift registers cycle through every possible binary value (with the exception of the zero vector), registers can be initialized to any state, with the exception of the zero vector.

</p>

<div class="mw-heading mw-heading3"><h3 id="Polynomial_interpretation">Polynomial interpretation</h3></div>

<p>A <a href="Polynomial" title="Polynomial">polynomial</a> over <a href="Galois_field" class="mw-redirect" title="Galois field">GF(2)</a> can be associated with the linear-feedback shift register. It has degree of the length of the shift register, and has coefficients that are either 0 or 1, corresponding to the taps of the register that feed the <a href="Xor" class="mw-redirect" title="Xor">xor</a> gate. For example, the polynomial corresponding to Figure 1 is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{4}+x+1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{4}+x+1}</annotation>

</semantics>

</math></span><img src="./81cc21c728e0955e3dcbe30797423c545104ac94.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.557ex; height:2.843ex;" alt="{\displaystyle x^{4}+x+1}" loading="lazy"></span>.

</p><p>A necessary and sufficient condition for the sequence generated by a LFSR to be maximal length is that its corresponding polynomial be <a href="Primitive_polynomial_(field_theory)" title="Primitive polynomial (field theory)">primitive</a>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Implementation">Implementation</h3></div>

<p>MLS are inexpensive to implement in hardware or software, and relatively low-order feedback shift registers can generate long sequences; a sequence generated using a shift register of length 20 is 2<sup>20</sup> − 1 samples long (1,048,575 samples).

</p>

<div class="mw-heading mw-heading2"><h2 id="Properties_of_maximum_length_sequences">Properties of maximum length sequences</h2></div>

<p>MLS have the following properties, as formulated by <a href="Solomon_Golomb" class="mw-redirect" title="Solomon Golomb">Solomon Golomb</a>.<sup id="cite_ref-golumb_4-0" class="reference"><a href="#cite_note-golumb-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Balance_property">Balance property</h3></div>

<p>The occurrence of 0 and 1 in the sequence should be approximately the same. More precisely, in a maximum length sequence of length <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}-1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n}-1}</annotation>

</semantics>

</math></span><img src="./51e4bd4ef2f9549d026cbf643a91c0d12a8c6794.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.384ex; height:2.509ex;" alt="{\displaystyle 2^{n}-1}" loading="lazy"></span> there are <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n-1}}</annotation>

</semantics>

</math></span><img src="./80c2cb3e3a7de902c9503fb34a17641df5896539.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.481ex; height:2.676ex;" alt="{\displaystyle 2^{n-1}}" loading="lazy"></span> ones and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n-1}-1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n-1}-1}</annotation>

</semantics>

</math></span><img src="./e25a81c69b84a7d496ffe9821e199ae004ad260a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.484ex; height:2.843ex;" alt="{\displaystyle 2^{n-1}-1}" loading="lazy"></span> zeros. The number of ones equals the number of zeros plus one, since the state containing only zeros cannot occur.

</p>

<div class="mw-heading mw-heading3"><h3 id="Run_property">Run property</h3></div>

<p>A "run" is a sub-sequence of consecutive "1"s or consecutive "0"s within the MLS concerned. The number of runs is the number of such sub-sequences.

</p><p>Of all the "runs" (consisting of "1"s or "0"s) in the sequence :

</p>

<ul><li>One half of the runs are of length 1.</li>

<li>One quarter of the runs are of length 2.</li>

<li>One eighth of the runs are of length 3.</li>

<div class="mw-heading mw-heading3"><h3 id="Correlation_property">Correlation property</h3></div>

<p>The circular <a href="Autocorrelation" title="Autocorrelation">autocorrelation</a> of an MLS is a <a href="Kronecker_delta" title="Kronecker delta">Kronecker delta</a> function<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> (with DC offset and time delay, depending on implementation). For the ±1 convention, i.e., bit value 1 is assigned <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=+1}</annotation>

</semantics>

</math></span><img src="./062261785446129907c44618616bc7c8dca7bd5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.16ex; height:2.343ex;" alt="{\displaystyle s=+1}" loading="lazy"></span> and bit value 0 <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=-1}</annotation>

</semantics>

</math></span><img src="./999944118796b0e4485e997249775b0d9925772f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.16ex; height:2.343ex;" alt="{\displaystyle s=-1}" loading="lazy"></span>, mapping XOR to the negative of the product:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(n)={\frac {1}{N}}\sum _{m=1}^{N}s[m]\,s^{*}[m+n]_{N}={\begin{cases}1&{\text{if }}n=0,\\-{\frac {1}{N}}&{\text{if }}0<n<N.\end{cases}}}">

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

</mfrac>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R(n)={\frac {1}{N}}\sum _{m=1}^{N}s[m]\,s^{*}[m+n]_{N}={\begin{cases}1&{\text{if }}n=0,\\-{\frac {1}{N}}&{\text{if }}0<n<N.\end{cases}}}</annotation>

</semantics>

</math></span><img src="./5c3c733c7432da2ff2c5dcb646712fad86a95194.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:56.924ex; height:7.343ex;" alt="{\displaystyle R(n)={\frac {1}{N}}\sum _{m=1}^{N}s[m]\,s^{*}[m+n]_{N}={\begin{cases}1&{\text{if }}n=0,\\-{\frac {1}{N}}&{\text{if }}0<n<N.\end{cases}}}" loading="lazy"></span>

</p><p>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s^{*}}</annotation>

</semantics>

</math></span><img src="./c0dd30e91ecca56ddf4ee71bf82b506b3249a5f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.145ex; height:2.343ex;" alt="{\displaystyle s^{*}}" loading="lazy"></span> represents the complex conjugate and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [m+n]_{N}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [m+n]_{N}}</annotation>

</semantics>

</math></span><img src="./a0b82c886262175ab1bb25fc393a865b5fd4e8e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.261ex; height:2.843ex;" alt="{\displaystyle [m+n]_{N}}" loading="lazy"></span> represents a <a href="Circular_shift" title="Circular shift">circular shift</a>.

</p><p>The linear autocorrelation of an MLS approximates a Kronecker delta.

</p>

<div class="mw-heading mw-heading2"><h2 id="Extraction_of_impulse_responses">Extraction of impulse responses</h2></div>

<p>If a <a href="LTI_system_theory" class="mw-redirect" title="LTI system theory">linear time invariant</a> (LTI) system's impulse response is to be measured using a MLS, the response can be extracted from the measured system output <i>y</i>[<i>n</i>] by taking its circular cross-correlation with the MLS. This is because the <a href="Autocorrelation" title="Autocorrelation">autocorrelation</a> of a MLS is 1 for zero-lag, and nearly zero (−1/<i>N</i> where <i>N</i> is the sequence length) for all other lags; in other words, the autocorrelation of the MLS can be said to approach unit impulse function as MLS length increases.

</p><p>If the impulse response of a system is <i>h</i>[<i>n</i>] and the MLS is <i>s</i>[<i>n</i>], then

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[n]=(h*s)[n].\,}</annotation>

</semantics>

</math></span><img src="./1b0da0dbee41ee90fcd53431e697b7212ac49730.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.098ex; height:2.843ex;" alt="{\displaystyle y[n]=(h*s)[n].\,}" loading="lazy"></span></dd></dl>

<p>Taking the cross-correlation with respect to <i>s</i>[<i>n</i>] of both sides,

</p>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\phi }_{sy}=h[n]*{\phi }_{ss}\,}</annotation>

</semantics>

</math></span><img src="./46b93ff2da18e3495897a7acddd25993963c162a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:16.073ex; height:3.176ex;" alt="{\displaystyle {\phi }_{sy}=h[n]*{\phi }_{ss}\,}" loading="lazy"></span></dd></dl>

<p>and assuming that φ<sub><i>ss</i></sub> is an impulse (valid for long sequences)

</p>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h[n]={\phi }_{sy}.\,}</annotation>

</semantics>

</math></span><img src="./dbd795d98fc94486378d66f18843cfa4b0c10bd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:11.366ex; height:3.176ex;" alt="{\displaystyle h[n]={\phi }_{sy}.\,}" loading="lazy"></span></dd></dl>

<p>Any signal with an impulsive autocorrelation can be used for this purpose, but signals with high <a href="Crest_factor" title="Crest factor">crest factor</a>, such as the impulse itself, produce impulse responses with poor <a href="Signal-to-noise_ratio" title="Signal-to-noise ratio">signal-to-noise ratio</a>. It is commonly assumed that the MLS would then be the ideal signal, as it consists of only full-scale values and its digital crest factor is the minimum, 0 dB.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> However, after <a href="Digital-to-analog_converter" title="Digital-to-analog converter">analog reconstruction</a>, the sharp discontinuities in the signal produce strong intersample peaks, degrading the crest factor by 4-8 dB or more, increasing with signal length, making it worse than a sine sweep.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> Other signals have been designed with minimal crest factor, though it is unknown if it can be improved beyond 3 dB.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Relationship_to_Hadamard_transform">Relationship to Hadamard transform</h2></div>

<p>Cohn and Lempel<sup id="cite_ref-cohn_11-0" class="reference"><a href="#cite_note-cohn-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> showed the relationship of the MLS to the <a href="Hadamard_transform" title="Hadamard transform">Hadamard transform</a>. This relationship allows the <a href="Correlation" title="Correlation">correlation</a> of an MLS to be computed in a fast algorithm similar to the <a href="Fast_Fourier_transform" title="Fast Fourier transform">FFT</a>.

</p>

<ul><li><a href="Barker_code" title="Barker code">Barker code</a></li>

<li><a href="Complementary_sequences" title="Complementary sequences">Complementary sequences</a></li>

<li><a href="Federal_Standard_1037C" title="Federal Standard 1037C">Federal Standard 1037C</a></li>

<li><a href="Frequency_response" title="Frequency response">Frequency response</a></li>

<li><a href="Impulse_response" title="Impulse response">Impulse response</a></li>

<li><a href="Polynomial_ring" title="Polynomial ring">Polynomial ring</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGolombGuang_Gong2005" class="citation book cs1">Golomb, Solomon W.; <a href="Guang_Gong" title="Guang Gong">Guang Gong</a> (2005). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=DhYXL4miZj4C"><i>Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar</i></a>. <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-82104-9</bdi>.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><cite id="CITEREFGembaVazquezFialkowskiEdelmann2021" class="citation journal cs1">Gemba, Kay L.; Vazquez, Heriberto J.; Fialkowski, Joseph; Edelmann, Geoffrey F.; Dzieciuch, Matthew A.; Hodgkiss, William S. (October 2021). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://asa.scitation.org/doi/10.1121/10.0006656">"A performance comparison between m-sequences and linear frequency-modulated sweeps for the estimation of travel-time with a moving source"</a></span>. <i>The Journal of the Acoustical Society of America</i>. <b>150</b> (4): <span class="nowrap">2613–</span>2623. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2021ASAJ..150.2613G">2021ASAJ..150.2613G</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1121%2F10.0006656">10.1121/10.0006656</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/34717519">34717519</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:240355915">240355915</a>.</cite></span>

</li>

<li id="cite_note-buracas-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-buracas_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFBuracas_GT,_Boynton_GM2002" class="citation journal cs1">Buracas GT, Boynton GM (July 2002). "Efficient design of event-related fMRI experiments using M-sequences". <i>NeuroImage</i>. <b>16</b> (3 Pt 1): <span class="nowrap">801–</span>13. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fnimg.2002.1116">10.1006/nimg.2002.1116</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/12169264">12169264</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7433120">7433120</a>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">"Linear Feedback Shift Registers-Implementation, M-Sequence Properties, Feedback Tables"<a rel="nofollow" class="external autonumber" href="http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm">[1]</a>, New Wave Instruments (NW), Retrieved 2013.12.03.</span>

</li>

<li id="cite_note-golumb-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-golumb_4-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFGolomb1967" class="citation book cs1">Golomb, Solomon W. (1967). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=LqtMAAAAMAAJ"><i>Shift register sequences</i></a>. Holden-Day. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-89412-048-4</bdi>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFJacobsenJuhl2013" class="citation book cs1">Jacobsen, Finn; Juhl, Peter Moller (2013-06-04). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=Sq6uFqlHg1gC"><i>Fundamentals of General Linear Acoustics</i></a>. John Wiley & Sons. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1118636176</bdi>. <q>A maximum-length sequence is a binary sequence whose circular autocorrelation (except for a small DC-error) is a delta function.</q></cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFSarwatePursley1980" class="citation journal cs1">Sarwate, D. V.; Pursley, M. B. (1980-05-01). "Crosscorrelation properties of pseudorandom and related sequences". <i>Proceedings of the IEEE</i>. <b>68</b> (5): <span class="nowrap">593–</span>619. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FPROC.1980.11697">10.1109/PROC.1980.11697</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0018-9219">0018-9219</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6179951">6179951</a>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://dspguru.com/dsp/tutorials/a-little-mls-tutorial">"A Little MLS (Maximum-Length Sequence) Tutorial | dspGuru.com"</a>. <i>dspguru.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2016-05-19</span></span>. <q>its RMS and peak values are both X, making its crest factor (peak/RMS) equal to 1, the lowest it can get.</q></cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.clear.rice.edu/elec301/Projects00/elec301/OtherTechniques/othertechniques.html">"Other Electro-Acoustical Measurement Techniques"</a>. <i>www.clear.rice.edu</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2016-05-19</span></span>. <q>The crest factor for MLS is very close to 1, so it makes sense to use this kind of input signal when we need a high signal-to-noise ratio for our measurement</q></cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFChan" class="citation web cs1">Chan, Ian H. <a rel="nofollow" class="external text" href="http://www.thinksrs.com/downloads/PDFs/ApplicationNotes/SR1_SweptSine.pdf">"Swept Sine Chirps for Measuring Impulse Response"</a> <span class="cs1-format">(PDF)</span>. <i>thinksrs.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2016-05-19</span></span>. <q>Maximum-length sequence (MLS) theoretically fits the bill because it has a mathematical crest factor of 0dB, the lowest crest factor possible. However, in practice, the sharp transitions and bandwidth-limited reproduction of the signal result in a crest factor of about 8dB</q></cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFFriese1997" class="citation journal cs1">Friese, M. (1997-10-01). <a rel="nofollow" class="external text" href="https://stanford.edu/~boyd/papers/pdf/multitone_low_crest.pdf">"Multitone signals with low crest factor"</a> <span class="cs1-format">(PDF)</span>. <i>IEEE Transactions on Communications</i>. <b>45</b> (10): <span class="nowrap">1338–</span>1344. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F26.634697">10.1109/26.634697</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0090-6778">0090-6778</a>.</cite></span>

</li>

<li id="cite_note-cohn-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-cohn_11-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFCohnLempel1977" class="citation journal cs1">Cohn, M.; Lempel, A. (January 1977). "On Fast M-Sequence Transforms". <i>IEEE Trans. Inf. Theory</i>. <b>23</b> (1): <span class="nowrap">135–</span>7. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.1977.1055666">10.1109/TIT.1977.1055666</a>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><cite id="CITEREFBristow-Johnson" class="citation web cs1">Bristow-Johnson, Robert. <a rel="nofollow" class="external text" href="http://www.dspguru.com/dsp/tutorials/a-little-mls-tutorial">"A Little MLS Tutorial"</a>.</cite> — Short on-line tutorial describing how MLS is used to obtain the <a href="Impulse_response" title="Impulse response">impulse response</a> of a <a href="Linear_time-invariant_system" title="Linear time-invariant system">linear time-invariant system</a>. Also describes how nonlinearities in the system can show up as spurious spikes in the apparent impulse response.</li>

<li><cite id="CITEREFHee" class="citation web cs1">Hee, Jens. <a rel="nofollow" class="external text" href="http://jenshee.dk/signalprocessing/mls.pdf">"Impulse response measurement using MLS"</a> <span class="cs1-format">(PDF)</span>.</cite> — Paper describing MLS generation. Contains C-code for MLS generation using up to 18-tap-LFSRs and matching Hadamard transform for impulse response extraction.</li>

<li><cite id="CITEREFSchäfer2012" class="citation web cs1">Schäfer, Magnus (October 2012). <a rel="nofollow" class="external text" href="http://www.ind.rwth-aachen.de/en/research/tools-downloads/aachen-impulse-response-database/">"Aachen Impulse Response Database"</a>. Institute of Communication Systems and Data Processing, RWTH Aachen University. V1.4.</cite> A (binaural) room impulse response database generated by means of maximum length sequences.</li>

<li><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf">"Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators — Obsolete"</a> <span class="cs1-format">(PDF)</span>. Xilinx. July 1996. XAPP052 v1.1.</cite> — Implementing lfsr's in FPGAs includes listing of taps for 3 to 168 bits</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-20" href="https://en.wikipedia.org/wiki/?title=Maximum_length_sequence&oldid=1296439931">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>